/****************************************************************
Hash ADT source file
Hashing function implementation
	Written By: Lam Lu
	Date: May/30/10
****************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include "model.h"
#include "lamHash.h"

#define MAX_STR 200



/**************************************************************************
This function allocates the array of structure
	Pre: arr_size
	Post: Array of Structure is allocated/created
	Return: address of array of structure
**************************************************************************/
HASH* buildHash( int arr_size)
{
	//Local Declarations
	HASH* ptr;
	int i, last;
		
	//Statements
	last = arr_size - 1;
	if(arr_size > 0)
	{
		ptr = (HASH*) calloc(arr_size, sizeof(HASH));
		if(ptr)
		{
			for(i=0; i <= last; ++i )
			{
				ptr[i].probe =0;
				ptr[i].remove = 0;
				ptr[i].pSoldier = '\0';
			}
		}
		return ptr;
	}
	return NULL;
}//end buildHash


/**************************************************************************
The function insert  data into HashArray
	Pre: pHash( pointer to HashArray), pointer to string
	Post: data inserted
	Return: 1 if success, 0 otherwise
	Preconditions: pHash, string, soldier have been read/declared
**************************************************************************/
int insertHash(HASH* pHash, char* string, void* dataIn, int arr_size)
{
	//Local Declarations	
	int index;
	int jumper = 1;
	int probe = 1;
	int success = 1;
		
	//Statements
	//store data into hash Arr
	index = calIndex(string, arr_size);
	if(!pHash[index].pSoldier)
	{
		pHash[index].pSoldier = dataIn;	
		pHash[index].probe = probe;
		pHash[index].remove = 0;
	}
	else
	{
		while((pHash[index].pSoldier) && probe < arr_size)
		{
			index = colResolution(index, &jumper, arr_size);
			probe++;
		}
		if(probe == arr_size)
			return (success = 0);

		pHash[index].pSoldier = dataIn;	
		pHash[index].probe = probe;
		pHash[index].remove = 0;
	}
	return success;	
}//end storeData

/*************************************************************************
The function searchs the data in Hash Array
	Pre: pHash( pointer to HashArray), key string, arr_size
	Reference parameters: targetIndex
	Post: targetIndex passed back to caller
	Return: 1 if found, 0 otherwise
	Preconditions: pHash, string, arr_size have been read
*************************************************************************/
int searchHash(HASH* pHash, char* string, int* targetIndex, int arr_size)
{
	//Local Declarations
	int probe = 1;
	int found;
	int jumper;
	int i, l;
	char tempName[MAX_STR] = {'\0'};
	char tempString[MAX_STR]={'\0'};

	//Statements
	(*targetIndex) = 0;
	(*targetIndex) = calIndex(string, arr_size);
	jumper = 1;

	l = strlen(string);
	for(i = 0; i < l; i++)
		tempString[i] = toupper(string[i]);

	if(pHash[*targetIndex].pSoldier)
	{
		strcpy(tempName,pHash[*targetIndex].pSoldier->name);
		l = strlen(tempName);	
		for(i = 0; i < l; i++)
			tempName[i] = toupper(tempName[i]);
	}
	

	
	if(pHash[*targetIndex].pSoldier && strcmp(tempName, tempString) == 0)// 
		found = 1;
	
	else
	{
		while((pHash[*targetIndex].pSoldier || pHash[*targetIndex].remove) && (probe < arr_size))
		{
			if(pHash[*targetIndex].pSoldier)
			{
				strcpy(tempName,pHash[*targetIndex].pSoldier->name);
				l = strlen(tempName);
				for(i = 0; i < l; i++)
					tempName[i] = toupper(tempName[i]);
				if(strcmp(tempName, tempString) == 0)
					break;
			}
			(*targetIndex) = colResolution(*targetIndex, &jumper, arr_size);
			probe++;
		}
		if((pHash[*targetIndex].pSoldier) && probe < arr_size)
			found = 1;
		else found = 0;
	}
	return found;
}//end searchHash

/*************************************************************************
The function deletes the data in Hash Array
	Pre: pHash( pointer to HashArray), key string, arr_size
	Reference parameters: deletedIndex, dataOut
	Post: target delelted, passed back the index of deleted target
		  and the pointer to target
	Return: 1 if success, 0 otherwise
	Preconditions: pHash, string, arr_size have been read
*************************************************************************/
int deleteHash(HASH* pHash, char* string, int* deletedIndex, void** dataOut,
			   int arr_size)
{
	//Local Declarations
	int success;

	//Statements
	success = searchHash(pHash, string, deletedIndex, arr_size);
	if(!success)
		return 0;
	else
	{
		pHash[*deletedIndex].remove = 1;
		*dataOut = pHash[*deletedIndex].pSoldier;
		pHash[*deletedIndex].pSoldier = '\0';
	}
	return success;

}//end deleteHash

/**************************************************************************
The function determines the index to use for hash array
	Pre: pointer to string , arr_size
	Post: index determined
	Return: int(index)
	Preconditions: string is not empty
**************************************************************************/
int calIndex(char* string, int arr_size)
{
   //Declarations
   int i, l, sum, index;
   char tempString[MAX_STR] = {'\0'};;

   //Statements
   sum = 0;
   l = strlen(string);
   for(i = 0; i < l; i++)
   {
	   tempString[i] = toupper(string[i]);
      sum += (int)tempString[i];
   }// for
   index = sum % arr_size;

   return index;
}// calIndex

/**************************************************************************
The function solves collision using Variation of Linear Probe resolution
. Add 1, subtract 2, add 3, subtract 4, and so forth. It returns an int 
number to determine the next step(add or subtract the index)
	Pre: current home address, arr_size
    Reference parameters: jumper( to determine subtraction or addition)
	Post: new index determined
	Return: new index
	Preconditions: none
**************************************************************************/
int colResolution (int index, int* jumper, int arr_size)
{
	//Local Definitions
	int last;
	int nextIndex;

	//Statements
	last = arr_size - 1;
	if((*jumper) % 2 == 1)
	{
		nextIndex = index + (*jumper);
		if(nextIndex > last)
			nextIndex = nextIndex - arr_size;		
	}
	else
	{
		nextIndex = index - (*jumper);
		if(nextIndex < 0)
			nextIndex = nextIndex + arr_size;
	}
	(*jumper)++;
	return nextIndex;
}//end colResolution

/**************************************************************************
The function calculates the efficiency of the hash function: load factor,
records have collisions, longest collision path 
	Pre: hash array, arr_size
	Post: efficiency calculated
	Return: loadFactor, collsionCount, longestCol
	Preconditions: hash array is not empty
**************************************************************************/
void getEfficiency(HASH* pHash, double* loadFactor, int* collisionCount, 
				   int* longestCol,int arr_size)
{
	//Local Definitions
	int i = 0;
	int last;
	int filledElems = 0;

	//Statements
	*loadFactor = 0;
	*collisionCount = 0;
	*longestCol = pHash[0].probe;
	last = arr_size - 1;
	while(i <= last)
	{
		if(pHash[i].pSoldier)
			filledElems++;
		if(pHash[i].probe > 1 && !(pHash[i].remove))
			(*collisionCount)++;
		if(pHash[i].probe > *longestCol && !(pHash[i].remove))
			*longestCol = pHash[i].probe;
		i++;

	}
	*loadFactor = ((filledElems * 1.0)/ arr_size) * 100;
	return;

}//end getEfficiency

/**************************************************************************
The function destroys hash array
	Pre: hash Array, pointer to function, arr_size
	Post: Hash destroyed
	Return: none
**************************************************************************/
void destroyHash(HASH* pHash, int arr_size, void (*freeMemory)(void* dataPtr))
{
	//Local Definitions
	HASH* pWalker, *pEnd;

	//Statements
	pEnd = pHash + arr_size;
	for(pWalker = pHash; pWalker < pEnd; pWalker++)
	{
		if(pWalker->pSoldier)
			freeMemory(pWalker->pSoldier);
	}
	free(pHash);
}//destroyHash

/**************************************************************************
The function frees my memory
	Pre: pointer to dataOut
	Post: Hash destroyed
	Return: none
**************************************************************************/
void freeMemory(SOLDIER* dataOut)
{
	
	free(dataOut->division);
	free(dataOut->jobCat);
	free(dataOut->name);
	free(dataOut->rank);
	free(dataOut);
}//end freeMemory
